package summary;

import java.util.*;

/**
 * @Author: 海琳琦
 * @Date: 2022/7/11 22:19
 */
public class Title1514 {

    static class State{
        int id;

        //i->j的最大概率
        double weight;

        public State(int id, double weight) {
            this.id = id;
            this.weight = weight;
        }
    }

    public static double maxProbability(int n, int[][] edges, double[] succProb, int start, int end) {
        //<i,<j, value>>
        Map<Integer, Map<Integer, Double>> graph = new HashMap<>();
        for (int i = 0; i < edges.length; i++) {
            int[] edge = edges[i];
            graph.computeIfAbsent(edge[0], g -> new HashMap<>()).put(edge[1], succProb[i]);
            graph.computeIfAbsent(edge[1], g -> new HashMap<>()).put(edge[0], succProb[i]);
        }
        //记录 i->j 之间的最大概率
        double[] prob = new double[n];
        prob[start] = 1.0;
        Queue<State> queue = new PriorityQueue<>((a, b) -> (Double.compare(b.weight, a.weight)));
        queue.offer(new State(start, 1));
        while (!queue.isEmpty()) {
            State state = queue.poll();
            int curId = state.id;
            double curWeight = state.weight;
            if (curId == end) {
                return curWeight;
            }
            if (curWeight < prob[curId]) {
                continue;
            }
            Map<Integer, Double> orDefault = graph.getOrDefault(curId, new HashMap<>());
            Set<Integer> integers = orDefault.keySet();
            for (Integer nextId : integers) {
                double nextWeight = orDefault.get(nextId) * prob[curId];
                if (nextWeight > prob[nextId]) {
                    prob[nextId] = nextWeight;
                    queue.offer(new State(nextId, nextWeight));
                }
            }
        }
        return 0.0;
    }

    public static void main(String[] args) {
        int n = 3;
        int[][] edges = {{0,1},{1,2},{0,2}};
        double[] succProb = {0.5,0.5,0.2};
        int start = 0, end = 2;
        maxProbability(n, edges, succProb, start, end);
    }
}
